package com.tys.algorithm.bak.code2;

import java.util.ArrayList;

public class Code12_DeleteGivenValue {

    public static class Node {
        public int value;
        public Node next;

        public Node(int data) {
            this.value = data;
        }
    }

    // head = removeValue(head, 2);
    //删除指定值：考虑重复值的情况
    public static Node removeValue(Node head, int num) {
        // head来到第一个不需要删的位置
        while (head != null) {
            if (head.value != num) {
                break;
            }
            head = head.next;
        }
        // 1 ) head == null
        // 2 ) head != null
        Node pre = head;
        Node cur = head;
        while (cur != null) {
            if (cur.value == num) {
                pre.next = cur.next;
            } else {
                pre = cur;
            }
            cur = cur.next;
        }
        return head;
    }


    //生成随机的链表
    public static Node generateRandomLinkedList(int len, int value) {
        int size = (int) (Math.random() * (len + 1));
        if (size == 0) {
            return null;
        }
        size--;
        Node head = new Node((int) (Math.random() * (value + 1)));
        Node pre = head;
        while (size != 0) {
            Node cur = new Node((int) (Math.random() * (value + 1)));
            pre.next = cur;
            pre = cur;
            size--;
        }
        return head;
    }

    //得到链表中随机的一个值
    public static int getRandomLinkedListValue(Node head) {
        if (head == null) {
            return 0;
        }
        ArrayList<Node> list = new ArrayList<>();
        while (head != null) {
            list.add(head);
            head = head.next;
        }

        int count = (int) (Math.random() * (list.size()));
//        System.out.println(count + " " + list.size());
        return list.get(count).value;
    }

    //检查是否删除成功
    public static boolean checkLinkedListRemove(Node head, int num) {
        while (head != null) {
            if (head.value == num) {
                return false;
            }
            head = head.next;
        }
        return true;
    }

    public static void main(String[] args) {
        int len = 50;
        int value = 100;
        int testTime = 100000;
        System.out.println("test begin!");
        for (int i = 0; i < testTime; i++) {
            Node node = generateRandomLinkedList(len, value);
            int num = getRandomLinkedListValue(node);
//            System.out.println(num);
            node = removeValue(node, num);
            if (!checkLinkedListRemove(node, num)) {
                System.out.println("Oops!");
                break;
            }
        }
        System.out.println("test end!");
    }
}
